10. Regular Expression Matching（Facebook Hard）

作者:

题目：Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character. '*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).
The function prototype should be:

bool isMatch(const char *s, const char *p)

Some examples:

isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("abc", ".*") → true
isMatch("aab", "c*a*b") → true

思路：'.'匹配任意单字符，但不能匹配空字符；'*'可以匹配0或多个前面一个字符，匹配0个就是将前面的字符删掉，匹配多个代表对前面字符的重复。'*'也可以匹配前面的’.’ 即’.*'可以代表一个'.’ 两个'.’ 或者多个'.’ 每一步匹配都会出现多种条件判别情况 我们用递归和动态规划来分别实现。

题解1:Recursion, 定义一个isMatch递归函数进行匹配，两个变量：s 和 p。先对 p 做条件判断，在此基础上，对 s 做条件判断。

条件1:p.length()==0, s为空返回true，s不空则返回false。

条件2:p.length()==1,

(2-1)s为空返回false；

(2-2)s不为空，p.charAt(0) == s.charAt(0)或者p.charAt(0) == '.'

若满足则返回isMatch(s.substring(1), p.substring(1))，否则为false。

条件3: P.length() >=2，

(3-1)s不空，p.charAt(1)!=’*’,且满足 s.charAt(0) == p.charAt(0) || p.charAt(0) == '.'时，若满足则返回isMatch(s.substring(1), p.substring(1))，否则为false。

(3-2)s不空，P.length() >=2 p.charAt(1)==’*’，且满足 s.charAt(0) == p.charAt(0) || p.charAt(0) == '.'时，如果该字符只出现一次 if (isMatch(s, p.substring(2))) 返回true，否则重复执行s = s.substring(1)

(3-3)p.charAt(1) == ’*’，返回isMatch(s, p.substring(2))。由上述，我们把条件2的最后一种情况和条件3的第一种情况合并。

Time: O((m+n)x2^(m+n/2)), m=s.length,n=p.length, Space: O(m^2 + n^2) 代码如下：

class Solution {
    public boolean isMatch(String s, String p) {
        if (p.length()==0) {
            return s.length()==0;
        }
        if (p.length() == 1 || p.charAt(1) != '*') {
            if (s.isEmpty() || (p.charAt(0) != '.' && p.charAt(0) != s.charAt(0))){
                return false;
            } else {
                return isMatch(s.substring(1), p.substring(1));
            }
        }
        while (!s.isEmpty() && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.')){  
            if (isMatch(s, p.substring(2))) { 
                return true;                     
            }                                    
            s = s.substring(1);
        }
        return isMatch(s, p.substring(2));
    }
}

题解2.DP

定义一个boolean dp[i][j]，用来表示s[0-i] 与p [0-j] 是否匹配。dp[0][0]表示两个空字符串是否匹配，初始化为true。dp[i][j]为true的条件如下：

条件1, s.charAt(i)=p.charAt(j)

条件2, p.charAt(j)=’.’

条件3, p.charAt(j)=’*’

(3-1)if p.charAt(j-1)!=s.charAt(i)，* matches zero of the preceding element. （后面有个例子）

(3-2)if p.charA(j-a)s.charAt(i),或者 p.charAt(j-1)’.’ * Matches or more of the preceding element

(3-2-1) . eg:(“aaab”, "aab") Matches or more of the preceding element, * Matches one

(3-2-2). eg:(“aaa”, “a*”) s.charAt(i-1)=p.charAt(j),* Matches multiple

(3-2-3). eg:(“aaab”, “ab*”) s.charAt(i)=p.charAt(j-1) ,* Matches zero

注意⚠：如右图所示，考虑到这种情况(“aab”, “cab”)中，c＊应匹配为空字符串，接下来应尝试匹配aab和a*b。这个子问题的解决应从对应空字符串的匹配开始，即dp[0][2]应设为true。 Time: O(mn),m=s.length,n=p.length Space: O(mn)

代码如下：

class Solution {
  public boolean isMatch(String s, String p) {
    if (s == null || p == null) {
        return false;
    }
     boolean[][]dp=new boolean[s.length()+1][p.length()+1];
     dp[0][0]= true;
     //提前考虑到这种情况("aab", "c*a*b")：将c＊删除，后即dp[0][2]为接下来的初始值，置为true 
     for(int i=0;i<p.length();i++){
         if(p.charAt(i)=='*'&& dp[0][i-1])
             dp[0][i+1]=true;
     }
     for(int i=0;i<s.length();i++){
         for(int j=0;j<p.length();j++ ){
            if(p.charAt(j)=='.'){
                dp[i+1][j+1]=dp[i][j];
            }
         
            if(p.charAt(j)==s.charAt(i)){
                dp[i+1][j+1]=dp[i][j];
            }
            if (p.charAt(j) == '*') {
                if (p.charAt(j-1) != s.charAt(i) && p.charAt(j-1) != '.') {
                    dp[i+1][j+1] = dp[i+1][j-1];
                }
                else {
                    dp[i+1][j+1] = (dp[i+1][j] || dp[i][j+1] || dp[i+1][j-1]);
                }
            }
        }
    }
    return dp[s.length()][p.length()];
  }
}